package com.algorithm.skiplist;

import java.util.ArrayList;
import java.util.Date;
import java.util.List;

public class SkipList<K extends Comparable<K>, V> {
	Node<K, V> head;
	int maxLevel;
	int level;
	double p = 0.5;
	Comparable<K> compare;

	public int statistic = 0;

	public SkipList(int maxLevel) {
		this.maxLevel = maxLevel;
		head = new Node<K, V>(this.maxLevel);
		level = 1;
	}

	public V find(K key) {
		Node<K, V> node = findMaxLessThen(key);
		node = node.forwards[0];
		if (node != null && key.compareTo(node.key) == 0) {
			return node.value;
		}
		return null;
	}

	protected Node<K, V> findMaxLessThen(K key) {
		Node<K, V> node = head;
		for (int i = level - 1; i >= 0; i--) {
			while (node.forwards[i] != null
					&& key.compareTo(node.forwards[i].key) > 0) {
				node = node.forwards[i];
			}
		}
		return node;
	}

	public List<V> findGE(K key, int offset, int limit) {
		List<V> values = new ArrayList<V>();

		Node<K, V> node = findMaxLessThen(key);
		if (node == null) {
			return values;
		}

		node = node.forwards[0];
		List<Node<K, V>> nodes = findGE(node, offset, limit);
		for (Node<K, V> n : nodes) {
			values.add(n.value);
		}
		return values;
	}

	protected List<Node<K, V>> findGE(Node<K, V> start, int offset, int limit) {
		List<Node<K, V>> nodes = new ArrayList<Node<K, V>>();
		Node<K, V> node = start;
		// 遍历本层
		while (offset > 0) {
			int i = level - 1;
			for (; i >= 0; i--) {
				if (node.forwards[i] != null) {
					break;
				}
			}

			for (; i >= 0; i--) {
				if (node.forwards[i] != null
						&& node.forwards[i].dises[i] <= offset) {
					node = node.forwards[i];
					offset -= node.dises[i];
					statistic++;
					break;
				}
			}
			if (i < 0) {
				break;
			}
		}

		if (offset > 0) {
			// 未找到
			return nodes;
		}

		// 找到了，遍历结果即可
		int counter = 0;
		while (counter < limit && node != null) {
			nodes.add(node);
			node = node.forwards[0];
			counter++;
		}
		return nodes;

	}

	public void insert(K key, V value) {
		Node<K, V> node = head;
		@SuppressWarnings("unchecked")
		Node<K, V>[] update = new Node[maxLevel];
		for (int i = level - 1; i >= 0; i--) {
			while (node.forwards[i] != null
					&& key.compareTo(node.forwards[i].key) > 0) {
				node = node.forwards[i];
			}
			update[i] = node;
		}

		if (node.forwards[0] != null
				&& key.compareTo(node.forwards[0].key) == 0) {
			node.forwards[0].value = value;
			return;
		}

		//
		int newLevel = randomLevel();
		newLevel = Math.min(newLevel, maxLevel);
		if (newLevel > level) {
			for (int i = level; i < newLevel; i++) {
				update[i] = head;
			}
			level = newLevel;
		}

		Node<K, V> newNode = new Node<K, V>(maxLevel);
		newNode.key = key;
		newNode.value = value;

		for (int i = 0; i < newLevel; i++) {
			newNode.forwards[i] = update[i].forwards[i];
			update[i].forwards[i] = newNode;
		}

		// 更新距离，用于分页和统计
		for (int i = 0; i < level; i++) {
			if (i < newLevel) {
				newNode.dises[i] = distance(update[i], newNode, i);
			}

			if (newNode.forwards[i] != null) {
				if (i < newLevel) {
					newNode.forwards[i].dises[i] -= newNode.dises[i] + 1;
				} else {
					newNode.forwards[i].dises[i]++;
				}
			}
		}
	}

	public void delete(K key) {
		Node<K, V> node = head;
		@SuppressWarnings("unchecked")
		Node<K, V>[] update = new Node[maxLevel];
		for (int i = level - 1; i >= 0; i--) {
			while (node.forwards[i] != null
					&& key.compareTo(node.forwards[i].key) > 0) {
				node = node.forwards[i];
			}
			update[i] = node;
		}
		node = node.forwards[0];
		if (node != null && key.compareTo(node.key) != 0) {
			return;
		}

		for (int i = 0; i < level; i++) {
			if (update[i].forwards[i] != node) {
				break;
			}
			update[i].forwards[i] = node.forwards[i];
		}

		for (int i = level - 1; i >= 0; i--) {
			if (head.forwards[i] == null) {
				level--;
				continue;
			}
			break;
		}

		// 更新距离，用于分页和统计
		for (int i = 0; i < level; i++) {
			if (update[i].forwards[i] != null) {
				if (update[i].forwards[i] != node.forwards[i]) {
					update[i].forwards[i].dises[i]--;
				} else {
					update[i].forwards[i].dises[i] += node.dises[i] - 1;
				}
			}
		}

	}

	int distance(Node<K, V> f, Node<K, V> t, int level) {
		int dis = 0;
		while (f != t) {
			f = f.forwards[0];
			dis++;
		}
		return dis;
	}

	int randomLevel() {
		int k = 1;
		while (Math.random() < p) {
			k++;
		}
		return k;
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = level - 1; i >= 0; i--) {
			Node<K, V> node = head;
			sb.append("level-" + (i + 1) + "");
			while (node.forwards[i] != null) {
				sb.append(toString(node.forwards[i], i));
				node = node.forwards[i];
			}
			sb.append("\n");
		}
		return sb.toString();
	}

	String toString(Node<K, V> node, int level) {
		String out = "";
		out = String.format("->(%s,%s,%s)", node.key, node.value,
				node.dises[level]);
		return out;
	}

	public static class Node<K extends Comparable<K>, V> {
		K key;
		V value;
		int[] dises;
		Node<K, V>[] forwards;

		@SuppressWarnings("unchecked")
		public Node(int maxLevel) {
			forwards = new Node[maxLevel];
			dises = new int[maxLevel];
		}

		public String toString() {
			String out = "";
			out = String.format("(%s,%s)", key, value);
			return out;
		}
	}

	public static void main(String[] args) {
		System.out.println(new Date());
		SkipList<Integer, Integer> sl = new SkipList<Integer, Integer>(14);
		for (int i = 0; i < 2000000; i++) {
			sl.insert(i, i);
			// System.out.println(sl);
		}
		System.out.println(new Date());
		for (int i = 0; i < 1000000; i++) {
			if (sl.find(i) != i) {
				System.out.println("BUG");
			}
			// System.out.println(sl);
		}
		System.out.println(new Date());
		// System.out.println(sl);
		for (int i = 0; i < 10; i += 2) {
			sl.delete(i);
			// System.out.println(sl);
		}
		//System.out.println(sl);
		System.out.println("visit counters = " + sl.statistic);
		System.out.println(sl.findGE(6, 500000, 20));
		System.out.println("visit counters = " + sl.statistic);
	}
}
